package class04;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: xw
 * @Create: 2022/3/8 16:48
 * @Description: 反转单链表
 */
public class ReverseSingleton {

    public static class Node{
        public int value;
        public Node next;

        public Node(int data){
            value = data;
        }
    }

    /**
     * 双链表
     */
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    /**
     * 反转单链表
     * @param head
     * @return
     */
    public static Node reverseLinkedList(Node head){
        Node pre = null;
        Node next = null;
        while(head != null){
            next = head.next;//记录下一个节点的位置
            head.next = pre;//给当前节点的指针逆序
            pre = head;//更新pre的位置
            head= next;//头指针后移
        }
        return pre;
    }



    /**
     * 反转双链表
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while(null != head){
            next = head.next;
            head.next = pre; //反转next指针
            head.last = next;//反转last指针
            pre =head;//跟新pre的值
            head = next;//跟新head
        }
        return pre;
    }

    /**
     * 得到双链表的最后一个节点
     * @param head
     * @return
     */
    public static DoubleNode testReverseDoubleList(DoubleNode head){
        if(null == head){
            return null;
        }
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (null != head){
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode pre = list.get(0);
        int N = list.size();
        for (int i = 1; i < N; i++) {
            DoubleNode cur = list.get(i);
            cur.last = null;
            cur.next = pre;
            pre.last = cur;
            pre = cur;
        }
        return list.get(N - 1);
    }

    /**
     * 得到单链表的最后一个节点
     * @param head
     * @return
     */
    public static Node testReverseLinkedList(Node head){
        if(null == head){
            return null;
        }
        ArrayList<Node> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        int N = list.size();
        for (int i = 1; i < N; i++) {
            list.get(i).next = list.get(i - 1);
        }
        return list.get(N - 1);

    }


    /**
     *  生成长度和最大值随机的单链表
     * @param len 最大长度
     * @param value 最大值
     * @return
     */
     public static Node generateRandomLinkedList(int len,int value){
         int size = (int)(Math.random() * (len+1));
         if(size == 0){
             return null;
         }
         size --;
         Node head = new Node((int)(Math.random()*(value +1)));
         Node pre = head;
         while(size != 0){
             Node cur = new Node((int)(Math.random()*(value +1)));
             pre.next = cur;
             pre = cur;
             size--;
         }
         return head;
     }
    public static DoubleNode generateRandomDoubleLinkedList(int len,int value){
        int size = (int)(Math.random() * (len+1));
        if(size == 0){
            return null;
        }
        size --;
        DoubleNode head = new DoubleNode((int)(Math.random()*(value +1)));
        DoubleNode pre = head;
        while(size != 0){
            DoubleNode cur = new DoubleNode((int)(Math.random()*(value +1)));
            pre.next = cur;
            cur.last = pre;
            pre = cur;
            size--;
        }
        return pre;
    }


     public static List<Integer> getLinkedListOriginOrder(Node node){
         List<Integer> ans = new ArrayList<>();
         while(null != node){
             ans.add(node.value);
             node = node.next;
         }
         return ans;
     }

    // for test
    public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.value);
            head = head.next;
        }
        return ans;
    }


    public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {


         return true;
    }



    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            Node node1 = generateRandomLinkedList(len, value);
            List<Integer> list1 = getLinkedListOriginOrder(node1);
            node1 = reverseLinkedList(node1);
            if (!checkLinkedListReverse(list1, node1)) {
                System.out.println("Oops1!");
            }

            Node node2 = generateRandomLinkedList(len, value);
            List<Integer> list2 = getLinkedListOriginOrder(node2);
            node2 = testReverseLinkedList(node2);
            if (!checkLinkedListReverse(list2, node2)) {
                System.out.println("Oops2!");
            }
        }
        System.out.println("test finish!");
    }
}
